package lc.q51_100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 */
public class Q51 {

    private int n;

    public List<List<String>> solveNQueens(int n) {
        this.n = n;
        List<List<String>> results = new ArrayList<>();
        // 一步步下，直到最后可以成功
        int[] step = new int[n];
        move(0, step, results);
        return results;
    }

    private void move(int nextStep,int[] had, List<List<String>> results) {
        //
        if (nextStep == n) {
            // 填充数字
            List<String> next = new ArrayList<>();
            for (int i : had) {
                char[] chars = new char[n];
                Arrays.fill(chars, '.');
                chars[i - 1] = 'Q';
                next.add(new String(chars));
            }
            results.add(next);
            return;
        }
        for (int i = 0; i < n; i++) {
            // 检测能否在当前棋子下子
            boolean canMove = true;
            // 横向不用检测，因为一步步下
            // 检测竖和斜
            for (int j = 0; j < nextStep; j++) {
                // 第一种情况就是如果上一层跟这一层的i相同
                // 第二种情况就是如果隔了一层，i也格了一个数
                if (had[j] == i + 1 ||
                        had[j] == (j - nextStep) + i + 1 ||
                        had[j] == (nextStep-j) + i + 1
                ) {
                    canMove = false;
                    break;
                }
            }
            if (canMove) {
                // 可以动，就动一个
                had[nextStep] = i + 1;
                move(nextStep+1, had, results);
            }
            had[nextStep] = 0;
        }
    }

    public static void main(String[] args) {
        Q51 q51 = new Q51();
        q51.n = 4;
        List<List<String>> lists = q51.solveNQueens(5);
        System.out.println(lists);
//        q51.move(3, new int[]{2,4,1,0}, new ArrayList<>());
    }

}
